package sort.mergesort;

import sort.insertsort.InsertSort;

import java.util.Arrays;

/**
 * @author XY
 * @version 1.0
 * @date 2021/9/6 17:10
 * @Description 归并排序
 */
public class MergeSort {
    private MergeSort(){

    }

    public static <E extends Comparable<E>> void sort(E[] arr){
        sort(arr,0,arr.length-1);
    }

    private static <E extends Comparable<E>> void sort(E[] arr,int l,int r){
        if(l>=r){
            return ;
        }
        int mid = l+(r-l)/2;
        sort(arr, l, mid);
        sort(arr,mid+1,r);
        merge(arr,l,mid,r);
    }


    public static <E extends Comparable<E>> void sort2(E[] arr){
        //优化3、减少内存开辟的控件
        E[] temp= Arrays.copyOf(arr,arr.length);

        sort2(arr,0,arr.length-1,temp);
    }

    private static <E extends Comparable<E>> void sort2(E[] arr,int l,int r, E[] temp ){
        if(l>=r){
            return ;
        }
        //优化二，当排序的区间较小时，可以用插入排序进行排序，因为数组小，那这个数组本身时有序数组的可能性就越大，
        //插入排序的时间复杂度再有序的情况下时O(n),这样就可以减少时间消耗
//        if(r-l <= 15){
//            InsertSort.insertSort(arr,l,r);
//            return;
//        }
        int mid = l+(r-l)/2;
        sort2(arr, l, mid,temp);
        sort2(arr,mid+1,r,temp);
        //优化1 ：对于两个区间只有前一个区间的最后一个值大于后一个的第一个值的时候才进行排序，因为每个区间都是有序的
        if(arr[mid].compareTo(arr[mid+1])>0){
            merge2(arr,l,mid,r,temp);
        }
    }

    //合并两个有序的区间arr[i]~arr[mid]和 arr[mid+1]~arr[r]
    private static <E extends Comparable<E>> void merge(E[] arr,int l,int mid,int r){

        E[] temp= Arrays.copyOfRange(arr,l,r+1);
        int i=l;
        int j=mid+1;
        for (int n=l;n<=r;n++) {
            if(i>mid){
                arr[n]=temp[j-l];
                j++;
            }else if(j>r){
                arr[n]=temp[i-l];
                i++;
            }else if (temp[i-l].compareTo(temp[j-l])<=0){
                //l代表偏移量
                arr[n]=temp[i-l];
                i++;
            }else{
                arr[n]=temp[j-l];
                j++;
            }
        }
    }

    //合并两个有序的区间arr[i]~arr[mid]和 arr[mid+1]~arr[r]
    //减少内存开辟的空间，不再每次merge都新开辟一个新数组
    private static <E extends Comparable<E>> void merge2(E[] arr,int l,int mid,int r,E[] temp){
        System.arraycopy(arr,l,temp, l ,r-l+1);
        int i=l;
        int j=mid+1;
        for (int n=l;n<=r;n++) {
            if(i>mid){
                arr[n]=temp[j];
                j++;
            }else if(j>r){
                arr[n]=temp[i];
                i++;
            }else if (temp[i].compareTo(temp[j])<=0){
                //l代表偏移量
                arr[n]=temp[i];
                i++;
            }else{
                arr[n]=temp[j];
                j++;
            }
        }
    }
}
